home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 050 / madtrb10.arc / GRAPH.DOC < prev    next >
Encoding:
Text File  |  1985-12-08  |  2.5 KB  |  69 lines
  1. The following is a pascal assignment that I had in data structures.  It
  2. implements a graph for analyzing data.  It is probably of use to you if you
  3. want to learn something about graph data structures.  Before digging into the
  4. code perhaps you want to get a book on data structures and read up on what a
  5. graph is.  Happy computing!!
  6.  
  7.                                                        Chris Maeder
  8.  
  9.  
  10.                            GRAPH ASSIGNMENT
  11.  
  12.                            Data  Structures
  13.                                Fall 1985
  14.  
  15. Write a Pascal program to find the minimum path length (distance) between
  16. various cities.  The input to the program will consist of three parts.  First
  17. is a list of edges (cities with a distance of one between them) from which
  18. the adjacency matrix can be constructed.  Finally is a list of cities for
  19. which you are to find distances.  Output will be the distances between the
  20. queries.
  21.  
  22. Input:
  23.  
  24.     Input starts with a list of city names, one per line.  These are the
  25.     labels of the nodes for the graph.  A 'ZZZ' on a line by itself ends the
  26.     list.
  27.  
  28.     After this comes pairs of city names giving the edges of the graph.  The
  29.     names are separated by one blank (no blanks occur within a name).  From
  30.     these pairs the adjacency matrix can be constructed.  The list of edges
  31.     is ended by a 'ZZZ ZZZ' on a line by itself.
  32.  
  33.     Finally come queries consisting of pairs of city names.  Find the minimum
  34.     path lengths for these pairs.  Read queries until the end of the file is
  35.     hit.
  36.  
  37.     Example input data:
  38.  
  39.          Milwaukee
  40.          Chicago
  41.          St_Louis
  42.          ZZZ
  43.          Milwaukee Chicago
  44.          St_Louis Milwaukee
  45.          ZZZ ZZZ
  46.          Chicago St_Louis
  47.  
  48. Output:
  49.  
  50.     Echo print everything read in.  Use labels.
  51.  
  52.     Print each pair of the query cities and give the path length between them.
  53.  
  54. Notes and Requirements:
  55.  
  56.     1.  The graph has at most 15 nodes (cities).
  57.     2.  The name of each city is at most 12 characters.
  58.     3.  There are at most 20 queries.
  59.     4.  The adjacency matrix must be a boolean array.
  60.     5.  A city found in the list of edges or in a query may not be in the
  61.         initial city list.  If so, print an error message, ignore that pair of
  62.         cities, and go on to the next pair of cities.
  63.     6.  It is possible no path will exist between some cities.
  64.     7.  The values in a cell change arbitrarily through the versions.  You
  65.         must catch the first occurrence of a 'true' in a cell to get the
  66.         minimum distance.
  67.  
  68.  
  69.